Probabilistic Domination in Random Graphs with Applications to Sensor Networks

Abstract

Energy-efficient strategies in wireless sensor networks (WSNs) need to achieve network coverage, network longevity, and they must be efficient in terms of energy. In practical terms probabilistic domination is a convenient tool that can be used to design systems that can monitor and control any network. This paper examines probabilistic domination in random graph including the Erdos Renyi and geometric random graphs, and also uses the results to make decisions, such as the clustering head selection within WSNs. Domination set tries are lower approximations to predicted levels of domination numbers, and threshold probabilities that are analytically determined and then validated by means of Monte Carlo trials as well as further indicate the distributions of domination sets of distinct network sizes and connectivity parameters. The use of greedy/randomized algorithms and approximate dominating sets are utilized and measures such as coverage probability, energy-saving capabilities, and network lifetime are evaluated. Results have shown that probabilistic domination is a better predictor of network coverage and the operational lifetime, and the greedy heuristics yield better results, in most cases. The method of coupling theoretical analysis with the simulation test-based validations evidences that probabilistic domination is a strong robust framework in designing energy-efficient, scalable and reliable WSNs. The findings extend the theoretical and practical relevance of the graph domination theory and its use in sensor networks.

Introduction

The text presents a comprehensive study of probabilistic domination in random graphs and its application to wireless sensor networks (WSNs). WSNs are crucial for smart cities, IoT, and resilient infrastructures, but face challenges in fault tolerance, coverage optimization, and energy-efficient network lifetime. These challenges are effectively modeled using graph domination theory.

The study integrates prior research on greedy heuristics, metaheuristics, genetic algorithms, and probabilistic graph analysis, highlighting domination-based methods as key tools for balancing coverage, connectivity, and energy efficiency in WSNs.

Two random graph models are used:

• Erd?s–Rényi random graphs (G(n,p)), which enable analytical derivation of domination thresholds and probabilistic bounds.

• Geometric Random Graphs (GRGs), which realistically model spatial deployment and communication constraints in WSNs.

The concept of probabilistic domination is introduced, defining the expected size of a dominating set and analyzing threshold edge probabilities (approximately ln?n/n\ln n / nlnn/n) at which domination is likely to occur. These thresholds indicate that larger networks require lower connectivity probabilities to achieve domination.

An algorithmic framework combines theoretical analysis (using first and second moment methods and Chernoff bounds) with Monte Carlo simulations to evaluate domination size, coverage probability, variance, and runtime. Simulations are conducted across varying network sizes, connectivity levels, and communication radii using greedy and randomized algorithms.

Finally, the framework is applied to WSNs by interpreting dominating nodes as cluster heads, enabling efficient data aggregation, full coverage, and improved energy efficiency. Overall, the work demonstrates that probabilistic domination provides a robust, scalable, and theoretically grounded approach for designing adaptive and sustainable wireless sensor network architectures.

Conclusion

In wireless sensor networks, this study showed that probabilistic domination provides a useful framework for estimating dominating set size, coverage probability, and network lifetime. The robustness of the method was validated by the close agreement between Monte Carlo simulations and analytical thresholds. While optimal cluster head selection extended network life, greedy heuristics further improved coverage and energy efficiency. All things considered, probabilistic dominance shows promise as a tool for creating scalable and energy-efficient WSNs.

References

[1] Hedar, A. R., Abdulaziz, S. N., Mabrouk, E., & El-Sayed, G. A. (2020). Wireless sensor networks fault-tolerance based on graph domination with parallel scatter search. Sensors, 20(12), 3509. [2] Bouamama, S., Blum, C., & Pinacho-Davidson, P. (2022). A population-based iterated greedy algorithm for maximizing sensor network lifetime. Sensors, 22(5), 1804. [3] Ghafouri, S., & Khasteh, S. H. (2020). A survey on exponential random graph models: an application perspective. PeerJ Computer Science, 6, e269. [4] Ghaffari, F., Bahrak, B., & Shariatpanahi, S. P. (2022). A novel approach to partial coverage in wireless sensor networks via the roman dominating set. IET Networks, 11(2), 58-69. [5] Sivakumar, N. R., Nagarajan, S. M., Devarajan, G. G., Pullagura, L., & Mahapatra, R. P. (2023). Enhancing network lifespan in wireless sensor networks using deep learning based Graph Neural Network. Physical Communication, 59, 102076. [6] Raczek, J. (2022). Polynomial algorithm for minimal (1, 2)-dominating set in networks. Electronics, 11(3), 300. [7] Dagdeviren, Z. A. (2020, April). A pure genetic energy-efficient backbone formation algorithm for wireless sensor networks in industrial Internet of Things. In The International Conference on Artificial Intelligence and Applied Mathematics in Engineering (pp. 553-566). Cham: Springer International Publishing. [8] Ahlawat, P., & Dave, M. (2021). An attack resistant key predistribution scheme for wireless sensor networks. Journal of King Saud University-Computer and Information Sciences, 33(3), 268-280. [9] Balbal, S., Bouamama, S., & Blum, C. (2021). A greedy heuristic for maximizing the lifetime of wireless sensor networks based on disjoint weighted dominating sets. Algorithms, 14(6), 170. [10] Othman, R. A., Darwish, S. M., & Abd El-Moghith, I. A. (2023). A multi-objective crowding optimization solution for efficient sensing as a service in virtualized wireless sensor networks. Mathematics, 11(5), 1128. [11] Rosati, R. M., Bouamama, S., & Blum, C. (2022, July). Construct, merge, solve and adapt applied to the maximum disjoint dominating sets problem. In Metaheuristics International Conference (pp. 306-321). Cham: Springer International Publishing. [12] Odor, G., & Thiran, P. (2021). Sequential metric dimension for random graphs. Journal of Applied Probability, 58(4), 909-951. [13] Wong, R., Chang, W. L., Chung, W. Y., & Vasilakos, A. V. (2023). Biomolecular and quantum algorithms for the dominating set problem in arbitrary networks. Scientific Reports, 13(1), 4205. [14] Yang, Z., Shi, M., & Wang, W. (2021). Greedy approximation for the minimum connected dominating set with labeling. Optimization Letters, 15(2), 685-700. [15] Oikonomou, K., Koufoudakis, G., Aïssa, S., & Stavrakakis, I. (2022). Probabilistic flooding performance analysis exploiting graph spectra properties. IEEE/ACM Transactions on Networking, 31(1), 133-146. [16] Dagdeviren, Z. A. (2021). Weighted connected vertex cover based energy-efficient link monitoring for wireless sensor networks towards secure internet of things. IEEE Access, 9, 10107-10119. [17] Ojeda, F., Mendez, D., Fajardo, A., & Ellinger, F. (2023). On wireless sensor network models: A cross-layer systematic review. Journal of sensor and actuator networks, 12(4), 50. [18] Skiadopoulos, K., Giannakis, K., Tsipis, A., Oikonomou, K., & Stavrakakis, I. (2020). Impact of drone route geometry on information collection in wireless sensor networks. Ad Hoc Networks, 106, 102220. [19] Tekawade, A., & Banerjee, S. (2023, August). Dominance maximization in uncertain graphs. In International Conference on Advanced Data Mining and Applications (pp. 231-246). Cham: Springer Nature Switzerland. [20] Kenyeres, M., & Kenyeres, J. (2021). Distributed flooding algorithm for sensor fusion in synchronous/asynchronous wireless sensor networks. In Proceedings of the Computational Methods in Systems and Software (pp. 527-539). Cham: Springer International Publishing. [21] Zhao, D., Xiao, G., Wang, Z., Wang, L., & Xu, L. (2020). Minimum dominating set of multiplex networks: Definition, application, and identification. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 51(12), 7823-7837. [22] Manman, L., Goswami, P., Mukherjee, P., Mukherjee, A., Yang, L., Ghosh, U., ... & Nkenyereye, L. (2021). Distributed artificial intelligence empowered sustainable cognitive radio sensor networks: A smart city on-demand perspective. Sustainable Cities and Society, 75, 103265. [23] Mo, S., Bao, Z., Zhang, P., & Peng, Z. (2020). Towards an efficient weighted random walk domination. Proceedings of the VLDB Endowment, 14(4), 560-572. [24] Doostmohammadian, M., & Charalambous, T. (2022, July). Distributed Anomaly Detection and Estimation over Sensor Networks: Observational-Equivalence and $ Q $-Redundant Observer Design. In 2022 European Control Conference (ECC) (pp. 460-465). IEEE. [25] Amutha, J., Sharma, S., & Nagar, J. (2020). WSN strategies based on sensors, deployment, sensing models, coverage and energy efficiency: Review, approaches and open issues. Wireless Personal Communications, 111(2), 1089-1115.

Copyright

Copyright © 2026 Athraa Talib Breesam, Hussein Jameel Mutashar, Mustafa Adil Hussein. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.